{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Shortest Unsorted Continuous Subarray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #greedy #array #two-pointers #sorting #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #贪心 #数组 #双指针 #排序 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findUnsortedSubarray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最短无序连续子数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> ，你需要找出一个 <strong>连续子数组</strong> ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。</p>\n",
    "\n",
    "<p>请你找出符合题意的 <strong>最短</strong> 子数组，并输出它的长度。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<div class=\"original__bRMd\">\n",
    "<div>\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,6,4,8,10,9,15]\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3,4]\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1]\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= nums.length <= 10<sup>4</sup></code></li>\n",
    "\t<li><code>-10<sup>5</sup> <= nums[i] <= 10<sup>5</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>进阶：</strong>你可以设计一个时间复杂度为 <code>O(n)</code> 的解决方案吗？</p>\n",
    "</div>\n",
    "</div>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [shortest-unsorted-continuous-subarray](https://leetcode.cn/problems/shortest-unsorted-continuous-subarray/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [shortest-unsorted-continuous-subarray](https://leetcode.cn/problems/shortest-unsorted-continuous-subarray/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,6,4,8,10,9,15]', '[1,2,3,4]', '[1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findUnsortedSubarray(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        nums_sorted = sorted(nums)\n",
    "        start = -1\n",
    "        end =-2\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]!=nums_sorted[i]:\n",
    "                end = i\n",
    "                if start==-1:\n",
    "                    start = i\n",
    "        return end -start +1\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findUnsortedSubarray(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        a, b = nums, sorted(nums)\n",
    "        i, j = 0, len(nums) - 1\n",
    "        while i < len(a) and a[i] == b[i]:\n",
    "            i += 1\n",
    "        while j > i and a[j] == b[j]:\n",
    "            j -= 1\n",
    "        return j+1-i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode.cn id=581 lang=python3\n",
    "#\n",
    "# [581] 最短无序连续子数组\n",
    "#\n",
    "# https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/description/\n",
    "#\n",
    "# algorithms\n",
    "# Easy (30.63%)\n",
    "# Total Accepted:    2.9K\n",
    "# Total Submissions: 9.6K\n",
    "# Testcase Example:  '[2,6,4,8,10,9,15]'\n",
    "#\n",
    "# 给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。\n",
    "# \n",
    "# 你找到的子数组应是最短的，请输出它的长度。\n",
    "# \n",
    "# 示例 1:\n",
    "# \n",
    "# \n",
    "# 输入: [2, 6, 4, 8, 10, 9, 15]\n",
    "# 输出: 5\n",
    "# 解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。\n",
    "# \n",
    "# \n",
    "# 说明 :\n",
    "# \n",
    "# \n",
    "# 输入的数组长度范围在 [1, 10,000]。\n",
    "# 输入的数组可能包含重复元素 ，所以升序的意思是<=。\n",
    "# \n",
    "# \n",
    "#\n",
    "class Solution:\n",
    "    def findUnsortedSubarray(self, nums: 'List[int]') -> 'int':\n",
    "        if not nums:\n",
    "            return 0\n",
    "\n",
    "        min_v = None\n",
    "        for i in range(len(nums)):\n",
    "            if min_v is not None:\n",
    "                if min_v > nums[i]:\n",
    "                    min_v = nums[i]\n",
    "            else:\n",
    "                if i < len(nums)-1 and nums[i] > nums[i+1]:\n",
    "                    min_v = nums[i+1]\n",
    "        \n",
    "        if min_v is None:\n",
    "            return 0\n",
    "\n",
    "        max_v = None\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            if max_v is not None:\n",
    "                if max_v < nums[i]:\n",
    "                    max_v = nums[i]\n",
    "            else:\n",
    "                if i > 0 and nums[i] < nums[i-1]:\n",
    "                    max_v = nums[i-1]\n",
    "        l = 0\n",
    "        for n in nums:\n",
    "            if min_v >= n:\n",
    "                l += 1\n",
    "            else:\n",
    "                break\n",
    "            \n",
    "\n",
    "        r = len(nums) - 1\n",
    "        for n in reversed(nums):\n",
    "            if max_v <= n:\n",
    "                r -= 1\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        return r - l + 1\n",
    "\n",
    "# if __name__ == \"__main__\":\n",
    "#     print(Solution().findUnsortedSubarray([2,1,0]))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findUnsortedSubarray(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        temp=copy.copy(nums)\n",
    "        temp.sort()\n",
    "        i,j=0,-1\n",
    "        \n",
    "        for k in range(len(temp)):\n",
    "            if temp[k]!=nums[k]:\n",
    "                i=k\n",
    "                break\n",
    "        \n",
    "        for k in range(len(temp)-1,-1,-1):\n",
    "            if temp[k]!=nums[k]:\n",
    "                j=k\n",
    "                break\n",
    "                \n",
    "        return j-i+1\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findUnsortedSubarray(self, nums: 'List[int]') -> 'int':\n",
    "        \n",
    "        if len(nums) <= 1:\n",
    "            return 0\n",
    "        else:\n",
    "            s = []\n",
    "            nums1 = sorted(nums)\n",
    "            for i in range(len(nums)):\n",
    "                if nums1[i] == nums[i]:\n",
    "                    pass\n",
    "                else:\n",
    "                    s.append(i)\n",
    "            if s == []:\n",
    "                return 0\n",
    "            else:\n",
    "                return s[-1] - s[0] + 1\n",
    "                          \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findUnsortedSubarray(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "#         if not nums:\n",
    "#             return 0\n",
    "#         temp_res = []\n",
    "#         start_index = len(nums)\n",
    "#         end_index = 0\n",
    "#         min_count = nums[0]\n",
    "#         # max_count = 0\n",
    "        \n",
    "#         for index,count in enumerate(nums):\n",
    "#             if not temp_res:\n",
    "#                 temp_res.append(count)\n",
    "#                 continue\n",
    "#             if count <= min_count:\n",
    "#                 start_index = min(start_index, index)\n",
    "#                 end_index = max(end_index, index)\n",
    "#             else:\n",
    "#                 min_count = count\n",
    "#             temp_res.append(count)\n",
    "            \n",
    "#         if end_index == 0 and start_index == len(nums):\n",
    "#             return 0\n",
    "#         else:\n",
    "#             return end_index - (start_index - 1) + 1\n",
    "        \n",
    "        _len, _sorted = len(nums), sorted(nums)\n",
    "        if nums == _sorted:\n",
    "            return 0\n",
    "        start_index  = min([index for index in range(_len) if nums[index] != _sorted[index]])\n",
    "        end_index  = max([index for index in range(_len) if nums[index] != _sorted[index]])\n",
    "        return end_index - start_index + 1 \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findUnsortedSubarray(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # Solution 1:\n",
    "        n = len(nums)\n",
    "        bag = -1\n",
    "        end = -2\n",
    "        \n",
    "        minn = nums[-1]\n",
    "        maxn = nums[0]\n",
    "        \n",
    "        for i in range(len(nums)):\n",
    "            maxn = max(maxn, nums[i])\n",
    "            minn = min(minn, nums[n - 1 - i])\n",
    "            \n",
    "            if nums[i] < maxn:\n",
    "                end = i\n",
    "            if nums[n - 1 - i] > minn:\n",
    "                bag = n - 1 - i\n",
    "            \n",
    "        return end - bag + 1\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findUnsortedSubarray(self, nums):\n",
    "        correct = [a==b for a,b in zip(nums, sorted(nums))]\n",
    "        if False not in correct:\n",
    "        \treturn 0\n",
    "        return len(nums) - correct.index(False) - correct[::-1].index(False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findUnsortedSubarray(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        sort_nums=sorted(nums)\n",
    "        \n",
    "        is_same=[a==b for a,b in zip(nums,sort_nums)]\n",
    "        \n",
    "        if all(is_same):\n",
    "            return 0\n",
    "        \n",
    "        return len(nums)-is_same.index(False)-is_same[::-1].index(False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findUnsortedSubarray(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        nums1 = sorted(nums)\n",
    "        l = len(nums)\n",
    "        if len(set(nums))==1: return 0\n",
    "        i = 0\n",
    "        while i<=l-1 and nums[i]==nums1[i]:\n",
    "            i+=1\n",
    "        j = l-1\n",
    "        while j>=0 and nums[j]==nums1[j]:\n",
    "            j-=1\n",
    "        return max(j-i+1,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findUnsortedSubarray(self, nums: 'List[int]') -> 'int':\n",
    "        start = end = -1\n",
    "        sorted_nums = sorted(nums)\n",
    "        l = len(nums)\n",
    "        for i in range(l):\n",
    "            if start < 0 and nums[i] != sorted_nums[i]:\n",
    "                start = i\n",
    "            if end < 0 and nums[l - i - 1] != sorted_nums[l - i -1]:\n",
    "                end = l - i - 1\n",
    "        if start < 0:\n",
    "            return 0\n",
    "        else:\n",
    "            return end - start + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findUnsortedSubarray(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        nums1=sorted(nums)\n",
    "        l,r=0,len(nums)-1\n",
    "        m,n=-1,-1\n",
    "        while (m==-1 or n==-1) and l<r:\n",
    "            if nums1[l]!=nums[l]:\n",
    "                m=l\n",
    "            else:\n",
    "                l+=1\n",
    "            if nums1[r]!=nums[r]:\n",
    "                n=r\n",
    "            else:\n",
    "                r-=1\n",
    "        if m==n==-1:return 0\n",
    "        return n-m+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findUnsortedSubarray(self, nums: List[int]) -> int:\n",
    "        length = len(nums)\n",
    "        if length == 0:\n",
    "            return 0\n",
    "        right = 0\n",
    "        max_right = nums[0]\n",
    "        for i in range(1, length):\n",
    "            if nums[i] >= max_right:\n",
    "                max_right = nums[i]\n",
    "            else:\n",
    "                right = i\n",
    "        left = length\n",
    "        min_left = nums[-1]\n",
    "        for i in range(length-2, -1, -1):\n",
    "            if nums[i] <= min_left:\n",
    "                min_left = nums[i]\n",
    "            else:\n",
    "                left = i\n",
    "        return right-left+1 if right-left+1>0 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findUnsortedSubarray(self, nums: List[int]) -> int:\n",
    "        nums2 = nums.copy()\n",
    "        nums2.sort()\n",
    "        p1 = 0\n",
    "        p2 = len(nums) - 1\n",
    "        while p1 <= p2 and nums2[p1] == nums[p1]:\n",
    "            p1 += 1\n",
    "        while p1 <= p2 and nums2[p2] == nums[p2]:\n",
    "            p2 -= 1\n",
    "        return p2 - p1 + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findUnsortedSubarray(self, nums: List[int]) -> int:\n",
    "        if len(nums)<=1:\n",
    "            return 0\n",
    "        left=0\n",
    "        right=len(nums)-1\n",
    "        maxm=nums[left]\n",
    "        minm=nums[right]\n",
    "        for i in range(1,len(nums)):\n",
    "            maxm=max(nums[i],maxm)\n",
    "            minm=min(nums[len(nums)-i-1],minm)\n",
    "            if nums[i]<maxm:\n",
    "                left=i\n",
    "            if nums[len(nums)-i-1]>minm:\n",
    "                right=len(nums)-i-1\n",
    "        return left-right+1 if left>right else 0\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findUnsortedSubarray(self, nums: List[int]) -> int:\n",
    "        # # 方法一\n",
    "        # diff = [i for i, (a, b) in enumerate(zip(nums, sorted(nums))) if a != b]\n",
    "        # if len(diff) > 0:\n",
    "        #     return max(diff) - min(diff) + 1\n",
    "        # else:\n",
    "        #     return 0\n",
    "        \n",
    "        # 方法二\n",
    "        nums_len = len(nums)\n",
    "        curr_max = nums[0]\n",
    "        curr_min = nums[nums_len-1]\n",
    "        left = 0\n",
    "        right = -1\n",
    "        # 寻找右边界\n",
    "        for i in range(nums_len):\n",
    "            if curr_max > nums[i]:\n",
    "                right = i\n",
    "            else:\n",
    "                curr_max = nums[i]\n",
    "        # 寻找左边界\n",
    "        for j in range(nums_len-1, -1, -1):\n",
    "            if curr_min < nums[j]:\n",
    "                left = j\n",
    "            else:\n",
    "                curr_min = nums[j]\n",
    "        return right - left + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findUnsortedSubarray(self, nums: List[int]) -> int:\n",
    "        max = nums[0]\n",
    "        min = nums[-1]\n",
    "        start = 0\n",
    "        end = -1\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] < max:\n",
    "                end = i\n",
    "            else:\n",
    "                max = nums[i]\n",
    "        for i in range(len(nums)-1,-1,-1):\n",
    "            if nums[i] > min:\n",
    "                start = i\n",
    "            else:\n",
    "                min = nums[i]\n",
    "        return end - start + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findUnsortedSubarray(self, nums: List[int]) -> int:\n",
    "        # nums_sorted=sorted(nums)\n",
    "        # nums_len=len(nums)\n",
    "        # l=0\n",
    "        # r=0\n",
    "        # for i in range(nums_len):\n",
    "        #     if nums[i]!=nums_sorted[i]:\n",
    "        #         l=i\n",
    "        #         break\n",
    "        # for j in range(nums_len-1,-1,-1):\n",
    "        #     if nums[j]!=nums_sorted[j]:\n",
    "        #         r=j\n",
    "        #         break\n",
    "        # return 0 if l==0 and r==0 else r-l+1\n",
    "        low=0\n",
    "        high=0\n",
    "        max_value=float(\"-inf\")\n",
    "        min_value=float(\"inf\")\n",
    "        nums_len=len(nums)\n",
    "        for i in range(nums_len):\n",
    "            if nums[i]<max_value:\n",
    "                high=i\n",
    "            max_value=max(max_value,nums[i]) \n",
    "        for j in range(nums_len-1,-1,-1):\n",
    "            if nums[j]>min_value:\n",
    "                low=j\n",
    "            min_value=min(min_value,nums[j])\n",
    "        print(high,low)\n",
    "        return 0 if low==0 and high==0 else high-low+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findUnsortedSubarray(self, nums: List[int]) -> int:\n",
    "        sort_nums = sorted(nums)\n",
    "        left = 0\n",
    "        right = len(nums) - 1\n",
    "        while left <= right and nums[left] == sort_nums[left]:\n",
    "            left += 1\n",
    "        while left <= right and nums[right] == sort_nums[right]:\n",
    "            right -= 1\n",
    "        return right - left + 1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findUnsortedSubarray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n < 2:\n",
    "            return 0\n",
    "        \n",
    "        max_num = nums[0]\n",
    "        right = 0\n",
    "        for i in range(1, n):\n",
    "            if nums[i] >= max_num:\n",
    "                max_num = nums[i]\n",
    "            else:\n",
    "                right = i\n",
    "        \n",
    "        min_num = nums[-1]\n",
    "        left = n-1\n",
    "        for j in range(n-2, -1, -1):\n",
    "            if nums[j] <= min_num:\n",
    "                min_num = nums[j]\n",
    "            else:\n",
    "                left = j\n",
    "        return max(0, right-left+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findUnsortedSubarray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        new_nums = list(zip(nums, list(range(n))))\n",
    "        new_nums.sort(key = lambda x: x[0])\n",
    "        left, right = 0, n-1\n",
    "        for i in range(n):\n",
    "            if left != new_nums[i][1]:\n",
    "                break\n",
    "            left += 1\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if right != new_nums[i][1]:\n",
    "                break\n",
    "            right -= 1\n",
    "        return right-left+1 if right > left else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findUnsortedSubarray(self, nums: List[int]) -> int:\n",
    "        arr = nums.copy()\n",
    "        arr.sort()\n",
    "        c = 0\n",
    "        left = float('inf')\n",
    "        right = 0\n",
    "        while nums :\n",
    "            if arr.pop() != nums.pop():\n",
    "                left = min([left,c])\n",
    "                right = max([right,c])\n",
    "            c +=1\n",
    "        return 0 if right<left else right-left+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findUnsortedSubarray(self, nums: List[int]) -> int:\n",
    "\n",
    "        if not nums:\n",
    "            return 0\n",
    "\n",
    "        res = 0\n",
    "        stack = []\n",
    "\n",
    "        numSorted = sorted(nums)\n",
    "\n",
    "        if numSorted == nums:\n",
    "            return 0\n",
    "\n",
    "        start = 0\n",
    "        end = len(nums) - 1\n",
    "\n",
    "        while nums[start]==numSorted[start]:\n",
    "            start += 1\n",
    "\n",
    "        while nums[end] == numSorted[end]:\n",
    "            end -= 1\n",
    "\n",
    "        return end - start + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findUnsortedSubarray(self, nums: List[int]) -> int:\n",
    "        diff = [i for i, (a, b) in enumerate(zip(nums, sorted(nums))) if a != b]\n",
    "        return len(diff) and max(diff) - min(diff) + 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findUnsortedSubarray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        def isSorted() -> bool:\n",
    "            for i in range(1, n):\n",
    "                if nums[i - 1] > nums[i]:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        if isSorted():\n",
    "            return 0\n",
    "        \n",
    "        numsSorted = sorted(nums)\n",
    "        left = 0\n",
    "        while nums[left] == numsSorted[left]:\n",
    "            left += 1\n",
    "\n",
    "        right = n - 1\n",
    "        while nums[right] == numsSorted[right]:\n",
    "            right -= 1\n",
    "        \n",
    "        return right - left + 1\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findUnsortedSubarray(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        max_num=nums[0]\n",
    "        right=0\n",
    "        for i in range(n):\n",
    "            if(nums[i]>=max_num):\n",
    "                max_num=nums[i]\n",
    "            else:\n",
    "                right=i\n",
    "        left=n\n",
    "        min_num=nums[-1]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if(nums[i]<=min_num):\n",
    "                min_num=nums[i]\n",
    "            else:\n",
    "                left=i\n",
    "        return right-left+1 if(right-left+1 >0) else 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findUnsortedSubarray(self, nums) -> int:\n",
    "        N = len(nums)\n",
    "        min_num = [0] * N\n",
    "        max_num = [0] * N\n",
    "        min_num[0] = nums[0]\n",
    "        max_num[N - 1] = nums[N - 1]\n",
    "        for i in range(0, N):\n",
    "            j = N - i - 1\n",
    "            if i > 0:\n",
    "                min_num[i] = max(min_num[i - 1], nums[i])\n",
    "            if j < N - 1:\n",
    "                max_num[j] = min(max_num[j + 1], nums[j])\n",
    "\n",
    "        while len(min_num) > 0 and min_num[0] == max_num[0]:\n",
    "            min_num = min_num[1:]\n",
    "            max_num = max_num[1:]\n",
    "            \n",
    "        while len(min_num) > 0 and min_num[-1] == max_num[-1]:\n",
    "            min_num = min_num[:-1]\n",
    "            max_num = max_num[:-1]\n",
    "        return len(max_num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findUnsortedSubarray(self, nums: List[int]) -> int:\n",
    "        right = 0\n",
    "        max_num = -float('inf')\n",
    "        for i, num in enumerate(nums):\n",
    "            if num >= max_num:\n",
    "                max_num = num\n",
    "            else:\n",
    "                right = i\n",
    "\n",
    "        left = 0\n",
    "        min_num = float('inf')\n",
    "        #for i, num in enumerate(list(reversed(nums))):\n",
    "        for i, num in reversed(list(enumerate(nums))):\n",
    "            if num <= min_num:\n",
    "                min_num = num\n",
    "            else:\n",
    "                left = i\n",
    "        return right - left + 1 if right > left else 0 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findUnsortedSubarray(self, nums: List[int]) -> int:\n",
    "        if len(nums)==1:\n",
    "            return 0\n",
    "        start=len(nums)-1\n",
    "        end=0    \n",
    "        maxn=99999\n",
    "        minn=-9999\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]>=minn:\n",
    "                minn=nums[i]\n",
    "            else:\n",
    "                end=i\n",
    "        for i in range(len(nums)-1,-1,-1):\n",
    "            if nums[i]<=maxn:\n",
    "                maxn=nums[i]\n",
    "            else:\n",
    "                start=i\n",
    "        if end-start+1>0:\n",
    "            return end-start+1\n",
    "        else:\n",
    "            return 0    \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # if len(nums)==1:\n",
    "        #     return 0\n",
    "        # start=len(nums)-1\n",
    "        # end=0\n",
    "        # maxn=99999\n",
    "        # minn=-9999\n",
    "        # for i in range(len(nums)):\n",
    "        #     if nums[i]>=minn: \n",
    "        #         minn=nums[i]\n",
    "        #     else:\n",
    "        #         end=i\n",
    "        # for i in range(len(nums)-1,-1,-1):\n",
    "        #     if nums[i]<=maxn:\n",
    "        #         maxn=nums[i]\n",
    "        #     else:\n",
    "        #         start=i\n",
    "        # if end-start+1>=0:\n",
    "        #     return end-start+1\n",
    "        # else:\n",
    "        #     return 0    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findUnsortedSubarray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        def isSorted() -> bool:\n",
    "            for i in range(1, n):\n",
    "                if nums[i - 1] > nums[i]:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        if isSorted():\n",
    "            return 0\n",
    "        \n",
    "        numsSorted = sorted(nums)\n",
    "        left = 0\n",
    "        while nums[left] == numsSorted[left]:\n",
    "            left += 1\n",
    "\n",
    "        right = n - 1\n",
    "        while nums[right] == numsSorted[right]:\n",
    "            right -= 1\n",
    "        \n",
    "        return right - left + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findUnsortedSubarray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 0  \n",
    "        # 思路：给原数组排序，再和新数组一个一个数字比较，当出现第一个位置相同但值不同的数字时，它就是左边界，\n",
    "        # 最后一个这样的数字就是右边界（可以逆向查找，那思路就和左边界一样）。\n",
    "        sorted_nums = sorted(nums, key=lambda x:x)\n",
    "        left = right = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] != sorted_nums[i]:\n",
    "                left = i\n",
    "                break\n",
    "        for j in range(n-1, -1, -1):\n",
    "            if nums[j] != sorted_nums[j]:\n",
    "                right = j + 1\n",
    "                break\n",
    "        return right - left\n",
    "                \n",
    "\n",
    "            \n",
    "            \n",
    "                        \n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
